package leetcode.code1670;

import java.util.Deque;
import java.util.LinkedList;

import leetcode.IDebug;

public class FrontMiddleBackQueue implements IDebug {

	Deque<Integer> q1, q2;

	public FrontMiddleBackQueue() {
		q1 = new LinkedList<>();
		q2 = new LinkedList<>();
	}

	public void pushFront(int val) {
		q1.addFirst(val);
	}

	public void pushMiddle(int val) {
		while (q1.size() != 0 && q1.size() >= q2.size()) {
			q2.addFirst(q1.pollLast());
		}
		while (q1.size() + 1 < q2.size()) {
			q1.addLast(q2.pollFirst());
		}
		q1.addLast(val);
	}

	public void pushBack(int val) {
		q2.addLast(val);
	}

	public int popFront() {
		return q1.size() == 0 ? q2.size() == 0 ? -1 : q2.pollFirst() : q1.pollFirst();
	}

	public int popMiddle() {
		while (q1.size() > q2.size()) {
			q2.addFirst(q1.pollLast());
		}
		while (q1.size() < q2.size()) {
			q1.addLast(q2.pollFirst());
		}
		return q1.size() == 0 ? -1 : q1.pollLast();
	}

	public int popBack() {
		return q2.size() == 0 ? q1.size() == 0 ? -1 : q1.pollLast() : q2.pollLast();
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub
		FrontMiddleBackQueue q = new FrontMiddleBackQueue();
		q.pushFront(1); // [1]
		q.pushBack(2); // [1, 2]
		q.pushMiddle(3); // [1, 3, 2]
		q.pushMiddle(4); // [1, 4, 3, 2]
		q.popFront(); // 返回 1 -> [4, 3, 2]
		q.popMiddle(); // 返回 3 -> [4, 2]
		q.popMiddle(); // 返回 4 -> [2]
		q.popBack(); // 返回 2 -> []
		q.popFront(); // 返回 -1 -> [] （队列为空）
	}

	@Override
	public void debug3() {
		FrontMiddleBackQueue q = new FrontMiddleBackQueue();
		q.pushMiddle(3); // [1, 3, 2]
		q.pushMiddle(4); // [1, 4, 3, 2]
		System.out.println(q.popBack());

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		FrontMiddleBackQueue so = new FrontMiddleBackQueue();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
